import java.util.ArrayList;
import java.util.List;

/**
 * 89. 格雷编码
 * https://leetcode-cn.com/problems/gray-code/
 */
public class Solutions_89 {
    public static void main(String[] args) {
        int n1 = 2;  // output: {0, 1, 3, 2}
        int n2 = 0;  // output: {0}
        int n3 = 1;  // output: {0, 1}
        int n4 = 3;  // output: {0, 1, 3, 2, 6, 7, 5, 4}

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);
        inputs.add(n4);

        for (Integer input : inputs) {
            List<Integer> res = grayCode(input);
            System.out.println(res);
        }
    }

    /**
     * 解法二：数学法
     * 格雷编码的生成过程：G(i) = i ^ (i / 2)
     * 0 ^ (0 / 2) = 000
     * 1 ^ (1 / 2) = 001
     * 2 ^ (2 / 2) = 010 ^ 001 = 011
     * 3 ^ (3 / 2) = 011 ^ 001 = 010
     */
    public static List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        if (n == 0) {
            res.add(0);
            return res;
        }
        if (n == 1) {
            res.add(0);
            res.add(1);
            return res;
        }
        int len = 1 << n;
        for (int i = 0; i < len; i++) {
            // 格雷编码的生成过程：G(i) = i ^ (i / 2)
            int code = i ^ (i / 2);
            res.add(code);
        }
        return res;
    }

    /**
     * 解法一：回溯法
     */
    public static List<Integer> grayCode2(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        if (n == 0) {
            return res;
        }
        if (n == 1) {
            res.add(1);
            return res;
        }
        int len = 1 << n;
        boolean[] visited = new boolean[len];
        visited[0] = true;

        backtrack(res, visited, 0, n);
        return res;
    }

    public static boolean backtrack(List<Integer> res, boolean[] visited, int cur, int n) {
        if (res.size() == visited.length) {
            return true;
        }
        for (int i = 0; i < n; i++) {
            // 异或 1 位，得到仅有一个位数差异的数值
            int next = cur ^ (1 << i);
            if (!visited[next]) {
                // next 未添加过，可以添加
                res.add(next);
                visited[next] = true;
                if (backtrack(res, visited, next, n)) {
                    return true;
                }
            }
        }
        return false;
    }
}
